package leetcode;

public class RotateFunction {

	public static void main(String[] args) {
		RotateFunction object = new RotateFunction();
		int[] arr = {4, 3, 2, 6};
		System.out.println(object.maxRotateFunction(arr));
	}
	
	/**
	// Given an array of integers A and let n to be its length.

	// Assume Bk to be an array obtained by rotating the array A k positions clock-wise, 
	// we define a "rotation function" F on A as follow:
	//for example : 4, 3, 2, 6 
	//B(0) : 6 4 3 2;  B(1) : 2 6 4 3

	// F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

	// Calculate the maximum value of F(0), F(1), ..., F(n-1)
	
	//这道题初看上出貌似得O(n),但是我们列一下式子
	//      a1,    a2,   a3, a4, a5, ...., a(n- 1)
	//F(0)  0      1      2   3   4  ....     n - 1
	//F(1) n - 1   0      1   2   3  ....     n - 2
	//F(2) n - 2  n - 1   0   1   2  ....     n - 3
	
	//其实上面的F(1)不是F(1)，实际是F(n - 1).因为旋转的方向问题，但这并不改变问题的本质。我只是为了方便说明情况这样写的
	//得出规律：F(i) = F(i - 1) - sum + a(i - 1) * n;
	 */
	
	public int maxRotateFunction(int[] A) {
		if(A == null || A.length <= 0){
			return 0;
		}
		int sum = 0;
		int last = 0;
		for(int  i = 0; i < A.length; i++){
			sum += A[i];
			last += i * A[i];
		}
		int res = last;
		int n = A.length;
		for(int  i = 1; i < A.length; i++){
			last = last - sum + A[i - 1] * n;
			res = Math.max(last, res);
		}
		return res;
	}
}
